//67:二进制求和
//给你两个二进制字符串，返回它们的和（用二进制表示）。
//
// 输入为 非空 字符串且只包含数字 1 和 0。
//
//
//
// 示例 1:
//
// 输入: a = "11", b = "1"
//输出: "100"
//
// 示例 2:
//
// 输入: a = "1010", b = "1011"
//输出: "10101"
//
//
//
// 提示：
//
//
// 每个字符串仅由字符 '0' 或 '1' 组成。
// 1 <= a.length, b.length <= 10^4
// 字符串如果不是 "0" ，就都不含前导零。
//
// Related Topics 位运算 数学 字符串 模拟 👍 815 👎 0
//TODO 太繁琐，感觉还有优化空间,注意数组越界

public class AddBinary {
    public static void main(String[] args) {
        String a = "1";
        String b = "111";
        System.out.println(addBinary(a, b));
    }

    public static String addBinary(String a, String b) {
        char[] aa = a.toCharArray();
        char[] bb = b.toCharArray();
        StringBuilder resultstr = new StringBuilder();
        if (aa.length > bb.length) {
            int add = 0;
            for (int i = 0; i < aa.length; i++) {
                if (i < bb.length) {
                    int bvalue = 0;
                    if (bb.length - 1 - i >= 0) {
                        bvalue = Integer.valueOf(bb[bb.length - 1 - i] + "");
                    }
                    int result = Integer.valueOf(aa[aa.length - 1 - i] + "") + bvalue + add;
                    if (result == 0) {
                        aa[aa.length - 1 - i] = '0';
                        add = 0;
                    } else if (result == 1) {
                        aa[aa.length - 1 - i] = '1';
                        add = 0;
                    } else if (result == 2) {
                        aa[aa.length - 1 - i] = '0';
                        add = 1;
                    } else if (result == 3) {
                        aa[aa.length - 1 - i] = '1';
                        add = 1;
                    }
                } else {
                    int result = Integer.valueOf(aa[aa.length - 1 - i] + "") + add;
                    if (result == 0) {
                        aa[aa.length - 1 - i] = '0';
                        add = 0;
                    } else if (result == 1) {
                        aa[aa.length - 1 - i] = '1';
                        add = 0;
                    } else if (result == 2) {
                        aa[aa.length - 1 - i] = '0';
                        add = 1;
                    } else if (result == 3) {
                        aa[aa.length - 1 - i] = '1';
                        add = 1;
                    }
                }
            }
            if (add == 1) {
                resultstr.append('1');
            }
            for (int i = 0; i < aa.length; i++) {
                resultstr.append(aa[i]);
            }
            return resultstr.toString();
        } else {
            int add = 0;
            for (int i = 0; i < bb.length; i++) {
                if (i < bb.length) {
                    int avalue = 0;
                    if (aa.length - 1 - i >= 0) {
                        avalue = Integer.valueOf(aa[aa.length - 1 - i] + "");
                    }
                    int result = Integer.valueOf(bb[bb.length - 1 - i] + "") + avalue + add;
                    if (result == 0) {
                        bb[bb.length - 1 - i] = '0';
                        add = 0;
                    } else if (result == 1) {
                        bb[bb.length - 1 - i] = '1';
                        add = 0;
                    } else if (result == 2) {
                        bb[bb.length - 1 - i] = '0';
                        add = 1;
                    } else if (result == 3) {
                        bb[bb.length - 1 - i] = '1';
                        add = 1;
                    }
                } else {
                    int result = Integer.valueOf(bb[bb.length - 1 - i] + "") + add;
                    if (result == 0) {
                        bb[bb.length - 1 - i] = '0';
                        add = 0;
                    } else if (result == 1) {
                        bb[bb.length - 1 - i] = '1';
                        add = 0;
                    } else if (result == 2) {
                        bb[bb.length - 1 - i] = '0';
                        add = 1;
                    } else if (result == 3) {
                        bb[bb.length - 1 - i] = '1';
                        add = 1;
                    }
                }
            }
            if (add == 1) {
                resultstr.append('1');
            }
            for (int i = 0; i < bb.length; i++) {
                resultstr.append(bb[i]);
            }
            return resultstr.toString();
        }
    }
}
